<?php

/*
 * Дерево типа "списки смежности", "Adjacency List"
 * ( проще: id-parentid)
 */

namespace T4\TREE;
use T4\Exception as Exception;

class ALTree extends ATree {
    
    /**
     * Сортировка дерева в $this->tree 
     */
    protected function sortData() {

	if ( empty($this->tree) || count($this->tree) == 0 )
	    return;
	
	/**
	 * Соберем дерево в блоки, по parent id
	 */
	$tree = array();
	
	foreach ( $this->tree as $node ) {
	    $tree[(int)(string)$node->pid][] = $node;
	};
	ksort($tree);
	
	/**
	 * Обнулим исходное дерево, в него будем складывать уже отсортированные элементы
	 */
	$this->tree = array();
	$idlevels = array();
	
	/**
	 * Работаем с корневыми элементами
	 * Вставляем их в результирующее дерево
	 * Задавая им заодно уровень = 0
	 */
	$nullLevelNodes = $tree[0];
	foreach ( $nullLevelNodes as $nullLevelNode ) {
	    $insert = &$this->tree[];
	    $insert = $nullLevelNode;
	    $insert->level = 0;
	    $id = (int)(string)$nullLevelNode->id;
	    $idlevels[$id] = 0;
	};
	unset($tree[0]);
	
	/**
	 * А теперь добавляем в нужные места оставшиеся элементы
	 */
	while ( !empty($tree) ) {
	    
	    /**
	     * На каждом шаге цикла ищем такой блок элементов,
	     * чей родитель уже добавлен в дерево
	     */
	    reset($tree);
	        
	    do {
		$block = each($tree);
		$parentID = $block['key'];
		$block = $block['value'];
	    } while ( !isset($idlevels[$parentID]) );

	    /**
	     * С блоком для вставки определились,
	     * теперь нужно найти для него место
	     */
	    $insertKey = -1;
	    foreach ( $this->tree as $key => $node ) {
		if ( (string)$node->id == $parentID ) {
		    $insertKey = $key;
		    break;
		}
	    }

	    /**
	     * Если нашли - ставим блок на новое место!
	     */
	    if ( -1 != $insertKey ) {
		
		/**
		 * Занесем новые элементы в список idLevels
		 * И назначим им уровни
		 */
		$newLevel = $idlevels[$parentID]+1;
		foreach ( $block as &$node ) {
		    $idlevels[(int)(string)$node->id] = $newLevel;
		    $node->level = $newLevel;
		}

		/**
		 * И теперь вставляем!
		 */
		foreach ( $block as $n ) {
		    $this->tree = array_merge(
			array_slice($this->tree, 0, $insertKey+1), 
			array( $n ),
			array_slice($this->tree, $insertKey+1)
		    );
		    ++$insertKey;
		};

		/**
		 * Убираем уже поставленный на место блок
		 */
		unset($tree[$parentID]);
		
	    }
	    	    
	}	
		
    }
        
}